package gold.gold02;

import java.util.HashMap;
import java.util.Map;

/**
 * 树, 递归, 路径值和
 * 妙。
 */
public class S0412求路径和 {
    /**
     * 12, 双递归。很耗时。写得还行。
     * 第一个递归, 递归把以每个节点为起点的符合sum要求的数量统计出来
     * 第二个递归, 通过递归求解上面的递归的每个值
     */
    public int pathSum(TreeNode root, int sum) {
        if(root == null) return 0;
        int result = startRootSum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
        return result;
    }
    // 以当前节点为起点的符合条件的路径的数量, 注意这里的统计既不需要传参也不需要设置全局变量
    // 因为这里有一个{根的返回 = 根是否可以 + 左子树的返回 + 右子树的返回}这么一个逻辑
    public int startRootSum(TreeNode node, int sum){
        if(node == null) return 0;
        if(node.val == sum){
            return 1 + startRootSum(node.left, 0) + startRootSum(node.right, 0);
        }else{
            return startRootSum(node.left, sum - node.val) + startRootSum(node.right, sum - node.val);
        }
    }

    /**
     * 路子很野。
     * 首先是两个全局的变量, ret是总的符合要求的数量, curSum记录了当前节点之前的每一个节点的和
     * 注意这里的curSum, 我们注意到dfs在递归的时候, 左子树和右子树都是n+1, 因此左右子树会修改同一个curSum[n]
     * 但是这个并不影响, 因为等计算右子树的时候, 左子树做的那一部分修改已经完全无所谓, 可以弃用了。
     * 这里仍然是一个递归+循环, pathSum函数并不递归, 只是拿来用一下。
     * 在dfs的递归中套了一个循环。
     */
    private int ret = 0;
    int[] curSum = new int[1000];
    public int pathSum2(TreeNode root, int sum) {
        if(root==null) return 0;
        if(root.val==sum) ret++;
        curSum[0] = root.val;
        dfs(root.left, 1, sum);
        dfs(root.right, 1, sum);
        return ret;
    }
    // 这里的n是层数, 表示当前这个node是第几层的, curSum记录了前面n层每一层的累计和
    // 这里给ret加上的是以当前节点为终节点的和为sum的个数, 并不会重复计数
    private void dfs(TreeNode root, int n, int sum) {
        if (root == null) return;
        curSum[n] = curSum[n-1] + root.val;
        if (curSum[n] == sum) ret++;
        // 此时curSum包括了从root到当前节点的每一步的路径和, 这里如果从之前的任何一个节点到当前节点距离是sum, 计数+1,
        for(int i=0; i<n; i++)
            if(curSum[n]-curSum[i]==sum)
                ret++;
        if(root.left!=null) dfs(root.left, n+1, sum);
        if(root.right!=null) dfs(root.right, n+1, sum);
    }

    /**
     * 没仔细看
     */
    public int pathSum3(TreeNode root, int sum) {
        // key是前缀和, value是大小为key的前缀和出现的次数
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        // 前缀和为0的一条路径
        prefixSumCount.put(0, 1);
        // 前缀和的递归回溯思路
        return recursionPathSum(root, prefixSumCount, sum, 0);
    }
    private int recursionPathSum(TreeNode node, Map<Integer, Integer> prefixSumCount, int target, int currSum) {
        // 1.递归终止条件
        if (node == null) {
            return 0;
        }
        // 2.本层要做的事情
        int res = 0;
        // 当前路径上的和
        currSum += node.val;
        //---核心代码
        // 看看root到当前节点这条路上是否存在节点前缀和加target为currSum的路径
        // 当前节点->root节点反推，有且仅有一条路径，如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了
        // currSum-target相当于找路径的起点，起点的sum+target=currSum，当前点到起点的距离就是target
        res += prefixSumCount.getOrDefault(currSum - target, 0);
        // 更新路径上当前节点前缀和的个数
        prefixSumCount.put(currSum, prefixSumCount.getOrDefault(currSum, 0) + 1);
        //---核心代码
        // 3.进入下一层
        res += recursionPathSum(node.left, prefixSumCount, target, currSum);
        res += recursionPathSum(node.right, prefixSumCount, target, currSum);

        // 4.回到本层，恢复状态，去除当前节点的前缀和数量
        prefixSumCount.put(currSum, prefixSumCount.get(currSum) - 1);
        return res;
    }
}
